#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/1/7 20:49|20:49
# @Author  : yangdingyi
# @File    : 1310. 子数组异或查询
# @Software: PyCharm
from typing import List


class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        la = len(arr)
        data = [{1: i} for i in arr]
        ll = 2
        while ll <= la:
            for i in range(la):
                if i + ll <= la:
                    ll2 = ll // 2
                    data[i][ll] = data[i][ll2] ^ data[i+ll2][ll2]
            ll *= 2
        ans = []
        for q in queries:
            x = q[0]
            n = q[1] - q[0] + 1
            ll = 1
            ai = 0
            while n:
                if n & 1:
                    ai ^= data[x][ll]
                    x += ll
                ll *= 2
                n //= 2
            ans.append(ai)
        return ans


solve = Solution()
arr = [4, 8, 2, 10]
queries = [[2, 3], [1, 3], [0, 0], [0, 3]]
print(arr)
print(solve.xorQueries(arr, queries))

print(0 ^ 6)
